#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
    vector<int> v;
    void Insert(int num) 
    {
        if (v.empty())
        {
            v.emplace_back(num);
        }
        else
        {
            auto it = lower_bound(v.begin(), v.end(), num);
            v.insert(it, num);
        }
    }

    double GetMedian() 
    {
        int sz = v.size();
        if (sz & 1)
        {
            return (double)(v[sz >> 1]);
        }
        else
        {
            return (double)(v[sz >> 1] + v[(sz - 1) >> 1]) / 2;
        }
    }

};

int main()
{
    vector<int> v{ 5,2,3,4,1,6,7,0,8 };
    Solution xz;

    for (auto e : v)
    {
        xz.Insert(e);
        cout << xz.GetMedian() << endl;
    }

	return 0;
}